/**
  * @file    :DoubleEndedQueue.hpp
  * @brief   :双端队列模板类实现
  * @author  :TMJ
  * @version :V1.0.0
  * @date    :2023-12-29
*/

#ifndef _QUEUE_DOUBLEENDEDQUEUE_H_
#define _QUEUE_DOUBLEENDEDQUEUE_H_

#include <iostream>

template<typename type>
class DoubleEndedQueue;

template<typename type>
std::ostream &operator<<(std::ostream &out, const DoubleEndedQueue<type> &src);

template<typename type>
class DoubleEndedQueue {

    friend std::ostream &operator<<<>(std::ostream &out, const DoubleEndedQueue<type> &src);

private:
    type *_data;  // 数据空间
    int _capacity;// 容量
    int _front;   // 头指针
    int _rear;    // 尾指针

public:
    // 指定容量的构造函数
    DoubleEndedQueue(int capacity = 20) : _capacity(capacity), _front(-1), _rear(-1) {
        this->_data = new type[this->_capacity];
        if (!this->_data) {
            throw std::bad_alloc();
        }
    }

    // 析构函数
    ~DoubleEndedQueue() {
        delete[] this->_data;
    }

    // 清空队列
    void Clear();

    // 判断栈满
    bool IsFull() const;

    // 入队（队头）
    bool PushFront(const type &data);

    // 出队（队尾）(保存数据)
    bool PopBack(type &data);

    // 出队（队尾）(不保存数据)
    bool PopBack();

    // 入队(队尾)
    bool PushBack(const type &data);

    // 出队(保存数据)（队头）
    bool PopFront(type &data);

    // 出队(不保存数据)（队头）
    bool PopFront();

    // 获取队头元素
    bool Front(type &data) const;

    // 获取队尾元素
    bool Rear(type &data) const;

    // 判断队空
    bool IsEmpty() const;

    // 获取队列长度
    int Length() const;
};

// 清空队列
template<typename type>
void DoubleEndedQueue<type>::Clear() {
    this->_rear = -1;
    this->_front = -1;
}

// 判断栈满
template<typename type>
bool DoubleEndedQueue<type>::IsFull() const {
    return this->Length() == this->_capacity;
}

// 入队（队头）
template<typename type>
bool DoubleEndedQueue<type>::PushFront(const type &data) {
    // 异常处理
    if (this->IsFull()) {
        return false;
    }

    // 空队特殊处理
    if (this->IsEmpty()) {
        this->_rear = 0;
    }

    // 计算新的头指针
    this->_front = (this->_front - 1 + this->_capacity) % this->_capacity;

    this->_data[this->_front] = data;

    return true;
}

// 出队（队尾）(保存数据)
template<typename type>
bool DoubleEndedQueue<type>::PopBack(type &data) {
    // 异常处理
    if (this->IsEmpty()) {
        return false;
    }

    data = this->_data[this->_rear];

    if (this - Length() == 1) {
        this->_rear = -1;
        this->_front = -1;
    } else {
        this->_rear = (this->_rear - 1 + this->_capacity) % this->_capacity;
    }

    return true;
}

// 出队（队尾）(不保存数据)
template<typename type>
bool DoubleEndedQueue<type>::PopBack() {
    // 异常处理
    if (this->IsEmpty()) {
        return false;
    }

    if (this->Length() == 1) {
        this->_rear = -1;
        this->_front = -1;
    } else {
        this->_rear = (this->_rear - 1 + this->_capacity) % this->_capacity;
    }

    return true;
}

// 入队(队尾)
template<typename type>
bool DoubleEndedQueue<type>::PushBack(const type &data) {
    // 异常处理
    if (this->IsFull()) {
        return false;
    }

    // 空队特殊处理
    if (this->IsEmpty()) {
        this->_front = 0;
    }

    // 计算新的头指针
    this->_rear = (this->_rear + 1 + this->_capacity) % this->_capacity;

    this->_data[this->_rear] = data;

    return true;
}

// 出队(保存数据)（队头）
template<typename type>
bool DoubleEndedQueue<type>::PopFront(type &data) {
    if (this->IsEmpty()) {
        return false;
    }

    data = this->_data[this->_front];

    if (this->Length() == 1) {
        this->_rear = -1;
        this->_front = -1;
    } else {
        this->_front = (this->_front + 1 + this->_capacity) % this->_capacity;
    }

    return true;
}

// 出队(不保存数据)（队头）
template<typename type>
bool DoubleEndedQueue<type>::PopFront() {
    if (this->IsEmpty()) {
        return false;
    }


    if (this->Length() == 1) {
        this->_rear = -1;
        this->_front = -1;
    } else {
        this->_front = (this->_front + 1 + this->_capacity) % this->_capacity;
    }

    return true;
}

// 获取队头元素
template<typename type>
bool DoubleEndedQueue<type>::Front(type &data) const {
    // 异常处理
    if (this->Length() == 0) {
        return false;
    }

    data = this->_data[this->_front];

    return true;
}

// 获取队尾元素
template<typename type>
bool DoubleEndedQueue<type>::Rear(type &data) const {
    // 异常处理
    if (this->Length() == 0) {
        return false;
    }

    data = this->_data[this->_rear];

    return true;
}

// 判断队空
template<typename type>
bool DoubleEndedQueue<type>::IsEmpty() const {
    if (this->_front == -1 && this->_rear == -1) {
        return true;
    }

    return false;
}

// 获取队列长度
template<typename type>
int DoubleEndedQueue<type>::Length() const {
    if (this->_rear == -1 && this->_front == -1) {
        return 0;
    }

    return (this->_rear - this->_front + 1 + this->_capacity) % this->_capacity;
}

// 重载 << 运算符
template<typename type>
std::ostream &operator<<(std::ostream &out, const DoubleEndedQueue<type> &src) {
    out << "The size of link queue: " << src.Length() << std::endl;

    for (int i = 0; i < src.Length(); i++) {
        int actual_index = (src._front + i + src._capacity) % src._capacity;
        out << src._data[actual_index] << std::endl;
    }

    return out;
}

#endif// _QUEUE_DOUBLEENDEDQUEUE_H_